﻿//-------------------------------------------------------------------
//	Copyright (c) 2010-2014  Zhirnov Andrey
//	This file is part of the "UX Standard Lib" project.
//	See copyright notice in "UX_STL_Core.h".
//-------------------------------------------------------------------
/*
	[ru] для всех сортировок:
			- сортируется от меньшего к большему
			- функция сравнения должна возвращать true если значение 1 больше значения 2
			  или наоборот, если нужна сортировка в обратном порядке
*/

#ifndef _UXS_SORT_FUNCTIONS_H
#define _UXS_SORT_FUNCTIONS_H

#pragma once

#include "../Types/Utils.h"
#include "TArray.h"
#include "TStaticArray.h"
#include "Algorithms.h"

namespace UX_STL
{
namespace UXTypes
{

	//
	// Sort Compare
	//

	template <typename T>
	struct TSortCmp
	{
		bool operator () (const T& val1, const T& val2)	const  { return val1 > val2; }
	};

	
#define SORT_FUNCTIONS( _name_ ) \
	template <typename T, typename S, typename A> \
	inline void _name_ (array<T,S,A> &sArray) \
	{ \
		TSortCmp<T>	cmp; \
		TSwap<T>	sw; \
		_name_##CS( sArray.ptr(), sArray.Count(), cmp, sw ); \
	} \
	\
	template <typename T, usize C, typename S> \
	inline void _name_ (static_array<T,C,S> &sArray) \
	{ \
		TSortCmp<T>	cmp; \
		TSwap<T>	sw; \
		_name_##CS( sArray.ptr(), sArray.Count(), cmp, sw ); \
	} \
	\
	template <typename T> \
	inline void _name_ (uni_array<T> sArray) \
	{ \
		TSortCmp<T>	cmp; \
		TSwap<T>	sw; \
		_name_##CS( sArray.ptr(), sArray.Count(), cmp, sw ); \
	} \
	\
	template <typename CmpOp, typename T, typename S, typename A> \
	inline void _name_ (array<T,S,A> &sArray, CmpOp cmp) \
	{ \
		TSwap<T>	sw; \
		_name_##CS( sArray.ptr(), sArray.Count(), cmp, sw ); \
	} \
	\
	template <typename CmpOp, typename T, usize C, typename S> \
	inline void _name_ (static_array<T,C,S> &sArray, CmpOp cmp) \
	{ \
		TSwap<T>	sw; \
		_name_##CS( sArray.ptr(), sArray.Count(), cmp, sw ); \
	} \
	\
	template <typename CmpOp, typename T> \
	inline void _name_ (uni_array<T> sArray, CmpOp cmp) \
	{ \
		TSwap<T>	sw; \
		_name_##CS( sArray.ptr(), sArray.Count(), cmp, sw ); \
	} \
	\
	template <typename CmpOp, typename SwapOp, typename T, typename S, typename A> \
	inline void _name_ (array<T,S,A> &sArray, CmpOp cmp, SwapOp sw) \
	{ \
		_name_##CS( sArray.ptr(), sArray.Count(), cmp, sw ); \
	} \
	\
	template <typename CmpOp, typename SwapOp, typename T, usize C, typename S> \
	inline void _name_ (static_array<T,C,S> &sArray, CmpOp cmp, SwapOp sw) \
	{ \
		_name_##CS( sArray.ptr(), sArray.Count(), cmp, sw ); \
	} \
	\
	template <typename CmpOp, typename SwapOp, typename T> \
	inline void _name_ (uni_array<T> sArray, CmpOp cmp, SwapOp sw) \
	{ \
		_name_##CS( sArray.ptr(), sArray.Count(), cmp, sw ); \
	}


/*
=================================================
	сортировка пузырьком	O(n^2)
=================================================
*/
	template <typename T, typename C, typename S>
	inline void BubbleSortCS (T * pArray, const usize uCount, C sCmp, S sSwap)
	{
		if ( uCount == 0 )
			return;

		uni_array<T>	arr( pArray, uCount );
		bool			b_flag = true;
		T				temp;

		while ( b_flag )
		{
			b_flag = false;
			for (usize i = 0; i < uCount-1; ++i)
			{
				if ( sCmp( arr[i], arr[i+1] ) )
				{
					sSwap( arr[i], arr[i+1], temp );
					b_flag = true;
				}
			}
		}

		sSwap.Clear( temp );
	}

	SORT_FUNCTIONS( BubbleSort );
		
/*
=================================================
	сортировка выборкой		O(n^2)
=================================================
*/
	template <typename T, typename C, typename S>
	inline void SelectSortCS (T * pArray, const usize uCount, C sCmp, S sSwap) 
	{
		if ( uCount == 0 )
			return;

		usize			a			= 0,
						b			= 0,
						c			= 0;
		bool			exchange	= false;
		T				temp;
		uni_array<T>	arr( pArray, uCount );
		
		for (a = 0; a < uCount-1; ++a)
		{
			exchange = false;
			c		 = a;
			temp	 = arr[a];

			for (b = a+1; b < uCount; ++b) 
			{
				if ( sCmp( temp, arr[b] ) )
				{
					c		 = b;
					exchange = true;
					sSwap.Set( temp, arr[b] );
				}
			}

			if ( exchange )
			{
				sSwap.Set( arr[c], arr[a] );
				sSwap.Set( arr[a], temp );
			}
		}

		sSwap.Clear( temp );
	}

	SORT_FUNCTIONS( SelectSort );

/*
=================================================
	сортировка вставкой		O(n^2)
=================================================
*/
	template <typename T, typename C, typename S>
	inline void InsertionSortCS (T * pArray, const usize uCount, C sCmp, S sSwap)
	{
		if ( uCount == 0 )
			return;

		isize			i	= 0;
		T				temp;
		uni_array<T>	arr( pArray, uCount );

		for (usize j = 1; j < uCount; ++j)
		{
			sSwap.Set( temp, arr[j] );
			i	 = j-1;

			while ( not sCmp( temp, arr[i] ) and i >= 0 )
			{
				sSwap.Set( arr[i+1], arr[i] );
				--i;
			}
			sSwap.Set( arr[i+1], temp );
		}
		
		sSwap.Clear( temp );
	}
	
	SORT_FUNCTIONS( InsertionSort );

/*
=================================================
	сортировка перемешиванием		O(n^2)
=================================================
*/
	template <typename T, typename C, typename S>
	inline void ShakerSortCS (T * pArray, const usize uCount, C sCmp, S sSwap)
	{
		if ( uCount == 0 )
			return;

		usize			i			= 0;
		bool			exchange	= false;
		T				temp;
		uni_array<T>	arr( pArray, uCount );

		do {
			exchange = false;

			for (i = uCount-1; i > 0; --i)
			{
				if ( not sCmp( arr[i], arr[i-1] ) )
				{
					sSwap( arr[i-1], arr[i], temp );
					exchange	= true;
				}
			}
			
			for (i = 1; i < uCount; ++i)
			{
				if ( not sCmp( arr[i], arr[i-1] ) )
				{
					sSwap( arr[i-1], arr[i], temp );
					exchange	= true;
				}
			}
		}
		while ( exchange );

		sSwap.Clear( temp );
	}
	
	SORT_FUNCTIONS( ShakerSort );

/*
=================================================
	сортировка методом Шелла	O(n * log^2(n))
=================================================
*/
	template <typename T, typename C, typename S>
	inline void ShellSortCS (T * pArray, const usize uCount, C sCmp, S sSwap)
	{
		if ( uCount == 0 )
			return;

		usize			i	= 0,
						gap	= 0;
		isize			j	= 0,
						k	= 0;
		T				temp;
		char			a[5] = { 8, 5, 3, 2, 1 };
		uni_array<T>	arr( pArray, uCount );

		for (k = 0; k < 5; ++k)
		{
			gap = a[k];

			for (i = gap; i < uCount; ++i)
			{
				sSwap.Set( temp, arr[i] );

				for (j = i-gap; (j >= 0) and sCmp( arr[j], temp ); j = j-gap)
				{
					sSwap.Set( arr[j+gap], arr[j] );
				}
				sSwap.Set( arr[j+gap], temp );
			}
		}

		sSwap.Clear( temp );
	}
	
	SORT_FUNCTIONS( ShellSort );

/*
=================================================
	сортировка по индексам диапазона	O(n log n)
=================================================
*/
	template <typename T, typename C, typename S>
	inline void _QuickSortCS (uni_array<T> sArray, const isize iLeft, const isize iRight, C sCmp, S sSwap)
	{
		isize	i = iLeft,
				j = iRight;

		T		temp1,
				temp2;

		sSwap.Set( temp1, sArray[ (iLeft + iRight)>>1 ] );

		do {
			while ( (i < iRight) and sCmp( temp1, sArray[i] ) )	++i;
			while ( (j > iLeft)  and sCmp( sArray[j], temp1 ) )	--j;
			
			if ( i <= j )
			{
				sSwap( sArray[i], sArray[j], temp2 );
				++i;
				--j;
			}
		}
		while( i <= j );

		if ( i < iRight )
			_QuickSortCS( sArray, i, iRight, sCmp, sSwap );

		if ( iLeft < j )
			_QuickSortCS( sArray, iLeft, j, sCmp, sSwap );

		sSwap.Clear( temp1 );
		sSwap.Clear( temp2 );
	}
	
	template <typename T, typename C, typename S>
	void QuickSortCS (T * pArray, const usize uCount, C sCmp, S sSwap)
	{
		if ( uCount == 0 )
			return;
		
		_QuickSortCS( uni_array<T>( pArray, uCount ), 0, uCount-1, sCmp, sSwap );
	}
	
	SORT_FUNCTIONS( QuickSort );

/*
=================================================
	сортировка по умолчанию
=================================================
*/
	template <typename T, typename C, typename S>
	inline void SortCS (T * pArray, const usize uCount, C sCmp, S sSwap)
	{
		QuickSortCS( pArray, uCount, sCmp, sSwap );
	}
	
	SORT_FUNCTIONS( Sort );
	
/*
=================================================
	сортировать индексы элементов массива
=================================================
*/
	template <typename CmpOp, typename T, typename I>
	inline void _SortIndices (const T* pArray, I* pIndices, const usize uCount, CmpOp cmp)
	{
		TypeDescriptor::MustBeInteger<I>();

		if ( uCount == 0 )
			return;

		usize	i	 = 0,
				gap	 = 0;
		isize	j	 = 0,
				k	 = 0;
		char	a[5] = { 8, 5, 3, 2, 1 };
		I		temp;

		uni_array<const T>	arr( pArray, uCount );
		uni_array<I>		idxs( pIndices, uCount );

		FOR( u, idxs ) {
			idxs[u] = u;
		}

		for (k = 0; k < 5; ++k)
		{
			gap = a[k];

			for (i = gap; i < uCount; ++i)
			{
				temp = idxs[i];

				for (j = i-gap; (j >= 0) and cmp( arr[ idxs[j] ], arr[ temp ] ); j = j-gap)
				{
					idxs[j+gap] = idxs[j];
				}

				idxs[j+gap] = temp;
			}
		}
	}

	template <typename ArrayType, typename IndicesArrayType>
	inline void SortIndices (const ArrayType &arr, IndicesArrayType &indices)
	{
		ASSERT( arr.Count() == indices.Count() );
		TSortCmp< ArrayType::value_t >	cmp;
		_SortIndices( arr.ptr(), indices.ptr(), Min( arr.Count(), indices.Count() ), cmp );
	}

	template <typename CmpOp, typename ArrayType, typename IndicesArrayType>
	inline void SortIndices (const ArrayType &arr, IndicesArrayType &indices, CmpOp cmp)
	{
		ASSERT( arr.Count() == indices.Count() );
		_SortIndices( arr.ptr(), indices.ptr(), Min( arr.Count(), indices.Count() ), cmp );
	}


#undef SORT_FUNCTIONS

//-------------------------------------------------------------------

}	// UXTypes
}	// UX_STL

#endif	// _UXS_SORT_FUNCTIONS_H